package com.lw.leetcode.sort.a;

/**
 * 414. 第三大的数
 *
 * @Author liw
 * @Date 2021/5/8 15:07
 * @Version 1.0
 */
public class ThirdMax {

    public static void main(String[] args) {
        ThirdMax test = new ThirdMax();
//        int[] arr = {3,2,4,1, 0};
//        int[] arr = {3,2,4,4,4,4,1, 0};
        int[] arr = {3};
        int i = test.thirdMax(arr);
        System.out.println(i);
    }

    public int thirdMax(int[] nums) {
        int length = nums.length;
        for(int i = (length >> 1) - 1; i >= 0; i--) {
            find(nums, i, length - 1);
        }
        int item = nums[0];
        int max = item;
        int n = 1;
        for (int i = 1; i < length; i++) {
            int it = nums[0];
            nums[0] = nums[length - i];
            nums[length - i] = it;
            find(nums, 0, length - i - 1);
            it = nums[0];
            if (it != item) {
                n++;
                item = it;
            }
            if (n == 3) {
                return it;
            }

        }
        return max;
    }

    private void find (int[] nums, int k, int limit) {
        int l = (k << 1) + 1;
        if (l > limit) {
            return;
        }
        int c = l + 1 > limit ? l : nums[l]> nums[l + 1] ? l : l + 1;
        if (nums[k] < nums[c]) {
            int item = nums[c];
            nums[c] = nums[k];
            nums[k] = item;
            find(nums, c, limit);
        }
    }
}
